// 请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

// 思路，单调递减栈，找右侧第一个大于该元素的位置
// 时间复杂度：O(n)，n是temperatures的长度
// 空间复杂度：O(n)，stack的大小

function dailyTemperatures(temperatures) {
    let res = new Array(temperatures.length).fill(0)
    let stack = [0]
    for (let i = 0; i < temperatures.length; i++) {
        while (stack.length && temperatures[stack[stack.length - 1]] < temperatures[i]) {
            let curIdx = stack.pop()
            res[curIdx] = i - curIdx
        }
        stack.push(i)
    }
    return res
}

let temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
console.log(dailyTemperatures(temperatures))